import java.util.Stack;

class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}

public class Test {
    /*
    题目1：反转链表
     */
    //方法一:自己的思路：用第三个变量记录 curNext.next
    public static ListNode ReverseList1(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }

        ListNode cur = head;
        ListNode curNext = cur.next;
        cur.next = null;

        while(curNext != null){
            ListNode record = curNext.next;
            curNext.next = cur;
            cur = curNext;
            curNext = record;
        }
            return cur;
        }

    //方法二：使用栈
    public static ListNode ReverseList(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }

        Stack<ListNode> stack = new Stack<>();
        ListNode cur = head;

        while(cur != null){
            stack.push(cur);
            cur = cur.next;
        }

        ListNode newhead = stack.pop();
        ListNode node = newhead;
        while(!stack.empty()){
            node.next = stack.peek();
            node = stack.pop();
        }
        node.next = null;
        return newhead;
    }

    public static void main1(String[] args) {
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(5);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        ListNode node = ReverseList(node1);
    }

    /*
    题目 2 ：合并两个有序链表
     */
    public static ListNode Merge(ListNode list1,ListNode list2) {
        if(list1 == null && list2 == null){
            return null;
        }else if(list1 == null){
            return list2;
        }else if(list2 == null){
            return list1;
        }

        ListNode head = null;

        ListNode cur1 = list1;
        ListNode cur2 = list2;
        if(cur1.val < cur2.val){
            head = cur1;
            cur1 = cur1.next;
        }else{
            head = cur2;
            cur2 = cur2.next;
        }

        ListNode node = head;
        while(cur1 != null && cur2 != null){
            if(cur1.val < cur2.val){
                node.next = cur1;
                node = cur1;
                cur1 = cur1.next;
            }else{
                node.next = cur2;
                node = cur2;
                cur2 = cur2.next;
            }
        }

        if(cur1 == null){
            node.next = cur2;
        }else{
            node.next = cur1;
        }
        return head;
    }

    public static void main2(String[] args) {
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node = Merge(node1, node2);
    }

    /*
    题目 3 ：删除有序链表中重复的元素
     */
    public ListNode deleteDuplicates1 (ListNode head) {
        if(head == null || head.next == null){
            return head;
        }

        ListNode cur = head;
        ListNode curNext = cur.next;
        while(curNext != null){
            if(cur.val != curNext.val){
                cur = curNext;
                curNext = curNext.next;
            }else{
                while(curNext != null && cur.val == curNext.val){
                    curNext = curNext.next;
                }
                cur.next = curNext;
            }
        }
        return head;
    }

    //参考官方答案，只利用了一个指针便能完成，修改我的答案：
    public ListNode deleteDuplicates (ListNode head) {
        if(head == null){
            return  head;
        }
        ListNode cur = head;
        while(cur != null && cur.next != null){
            if(cur.val == cur.next.val){
                //如果 cur 与 cur.next 的值相同
                //那么只需要修改 cur.next 的值即可
                cur.next = cur.next.next;
            }else{
                //当 cur 与 cur.next 的值不相同时
                //再让 cur 去指向 cur.next 的位置，并不一定是紧挨着的
                cur = cur.next;
            }
        }
        return head;
    }

    /*
    题目 4：链表中倒数 k 个结点
     */
    //快慢指针
    public ListNode FindKthToTail1 (ListNode pHead, int k) {
        if(pHead == null || k == 0){
            return null;
        }

        ListNode slow = pHead;
        ListNode fast = pHead;

        while(k - 1 > 0 && fast.next != null){
            fast = fast.next;
            k--;
        }

        if(k - 1 > 0){
            return null;
        }

        while(fast.next != null){
            slow = slow.next;
            fast = fast.next;
        }

        return slow;
    }

    public ListNode FindKthToTail (ListNode pHead, int k) {
        ListNode slow = pHead;
        ListNode fast = pHead;
        // k 是多少，fast 就从 pHead 往后走多少步
        for(int i = 0; i < k; i++){
            if(fast != null){
                fast = fast.next;
            }else{
                // k 的值大于链表的长度，返回 null 即可
                return null;
            }
        }

        while(fast != null){
            slow = slow.next;
            fast = fast.next;
        }

        return slow;
    }

    /*
    题目 5 ：链表的奇偶重排
     */
    //双指针：
    public static ListNode oddEvenList (ListNode head) {
        if(head == null || head.next == null || head.next.next == null){
            return head;
        }

        //链表中有三个或以上的结点
        ListNode oddHead = head;
        ListNode evenHead = head.next;

        ListNode cur1 = oddHead;
        ListNode cur2 = evenHead;

        while(cur1.next != null && cur2.next != null){
            cur1.next = cur2.next;
            cur1 = cur2.next;
            cur2.next = cur1.next;
            cur2 = cur1.next;
        }

        cur1.next = evenHead;

        return oddHead;
    }

    public static void main(String[] args) {
        ListNode node1 = new ListNode(2);
        ListNode node2 = new ListNode(1);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(5);
        ListNode node5 = new ListNode(6);
        ListNode node6 = new ListNode(4);
        ListNode node7 = new ListNode(7);

        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        node5.next = node6;
        node6.next = node7;
        ListNode node = oddEvenList(node1);
    }

    
}
